The Infona portal uses cookies, i.e. strings of text saved by a browser on the user's device. The portal can access those files and use them to remember the user's data, such as their chosen settings (screen view, interface language, etc.), or their login data. By using the Infona portal the user accepts automatic saving and using this information for portal operation purposes. More information on the subject can be found in the Privacy Policy and Terms of Service. By closing this window the user confirms that they have read the information on cookie usage, and they accept the privacy policy and the way cookies are used by the portal. You can change the cookie settings in your browser.
A new method for verification of programs is proposed. The main idea is to reduce assertions about programs to the problem of reachability. It is shown in [1] that the reachability problem is algorithmically solvable for a wide class of programs.
The paper describes a method of the systematic development of programs supplemented by specifications. A program in our sense consists of an instruction (the virtual program) plus the specification which in turn consists of a precondition, a postcondition and a set of assertions. Such a program is called correct if the instruction is totally correct wrt the pre- and postcondition, if it does not abort...
In this paper we study the relative succinctness of different representations of deterministic polynomial time languages and investigate what can and cannot be formally verified about these representations. We also show that the relative succinctness of different representations of languages is directly related to the separation of the corresponding complexity classes; for example, PTIME ≠ NPTIME...
This paper presents a discussion and summary of results obtained jointly with K.Culik [1] and M.Nivat [2]. The idea of public key systems as applicable to information systems is reviewed. The development of information systems based on the new concept of encryption triple is outlined. Although the construction of encryption triples using number-theoretic tools is possible, systems of encryption...
Traditional formal proof systems have been found unusable by those working on such applications of logic as program verification. They demand too much from the proof generator and too little from the proof checker. The notion of proof sketch or informal proof is an unsatisfactory substitute both because it is imprecise and because it treats the symptom rather than the disease. We propose to replace...
The present paper gives an overview of grammar and L form theory as of January 31, 1979. It is intended to complement Ginsburg's 1977 survey of grammar forms [G]. Hence although we present some new results on grammar forms the main thrust of the paper is to survey L forms. The number of papers in this area is now over 65, see [W1] hence it may be observed that this is indeed a fast developing...
Thm 1 states a negative result about the classical semantics of program schemes. Thm 2 investigates the reason for this. We conclude that Thm 2 justifies the Henkin-type semantics ⊨ for which the opposite of the present Thm 1 was proved in Andréka-Németi[1],
Set the date range to filter the displayed results. You can set a starting date, ending date or both. You can enter the dates manually or choose them from the calendar.